COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	1 Dec. 1974	GENERATING ARCS ON RASTER DEVICES	L. Earnest
C00011 ENDMK
C⊗;
1 Dec. 1974	GENERATING ARCS ON RASTER DEVICES	L. Earnest

This note looks for efficient ways to represent and generate arcs
of arbitrary curves "on the fly" for raster devices such as the
XGP.  Whether in software or hardware, the inner loop should be
quite small, so that we can put up a lot of lines at once.  I
consider here n-th order difference equations.

			A "PERFECT" CIRCLE
To test alternative schemes, consider the problem of representing
a circle of outer radius r with line width a.  In a coordinate
system with origin at the center of the circle, the outer circle
satisfies
(1)	x↑2 + y↑2 = r↑2
and the inner circle is
(2)	x↑2 + y↑2 = (r-a)↑2

To represent the circle (or any curve, for that matter) in raster
coordinates, we must generate a series of triples of the form X[i],
Y[i], W[i], where the X and Y are the raster coordinates of the left
edge of the line at the i-th slice and W is the line width there. 

To represent a full circle, we need to represent four arcs, namely
the left and right parts, where the raster lines intersect the sides
of the circle, and the top and bottom, where the raster lines intersect
the outer circle, but not the inner one.  We can solve (1) and (2),
above, to find the x coordinate of the left edge and the line width W
for any given y coordinate:
(3)	x = -sqrt(r↑2 - y↑2)			[left side, top, and bottom]
(4)	x = sqrt((r-a)↑2 - y↑2)			[right side]

(5)	W = 2*|x|				[top and bottom]
(6)	W = sqrt(r↑2 - y↑2) - sqrt((r-a)↑2 -y↑2)	[both sides]

We can convert to XGP coordinates (X,Y), where Y is inverted and
increases by one for each raster line counting from top to
bottom, by making the following substitutions in the above equations:
(7)	x = X - Xo
(8)	y = -(Y - Yo)
where (Xo,Yo) are the XGP coordinate of the center of the circle.
This is left as an exercise for the reader.

			DIFFERENCE APPROXIMATIONS
Calculations such as the one above are too complex to perform while
synthesizing an XGP raster.  Our current XGP service permits you to
specify line segments in terms of X, Y, W, delta X, and number of
repetitions N.  That is, X is represented as a first order difference
equation and W is constant in any given segment.  This scheme is
well-suited to representing straight lines, but forces more complex
curves to be represented by straight line segments.

We consider here a generalization of this scheme in which both X and
W are permitted to have higher order differences associated with
them.  This presumably reduces the number of segments needed to
represent any given curve, and thus the amount of computational
overhead involved in starting and finishing segments, but increases
the amount of computation in the "inner loop" of raster synthesis.
The inner loop for n-th order differences would look something like
	...
LOOP:	move A,[<n-th difference>]
	addb A,[<(n-1)-th difference>]
	...
	addb A,[<1st difference>]
	addb A,[<variable>]
	<output it>
	AOBJN N,LOOP

The question then becomes, what is the optimum number of differences
to use for X and W (i.e. the combination that results in the smallest
amount of computation in the critical path) for useful curves. 

I have written a program to test the efficiency of various approximations
as representations of semicircles.  It works by doing least-square
fits to the given curve with an n-th polynomial and seeing how far
it can go in Y while still fitting X and W with specified tolerance
(one raster unit, in the examples below).  An n-th order polynomial
is, of course, exactly equivalent to an n-th order difference equation,
though the coefficients are different.

The test program is somewhat suboptimal in that it uses least squares
rather than minimax (Chebyshev) approximation, but it is a lot simpler
and faster than an optimum solution would be.  The tables below show
the number of segments needed to represent two different sizes of circle.
Uninteresting (i.e. very inefficient) cases are marked with "-".

	r (radius) = 600 pixels (3 inches on XGP)
	a (line width) = 5 pixels

W differences →   0    1    2    3

X differences ↓
	      0	477  481    -	 -

	      1  66   42   42    -
					← number of segments needed
	      2  54   19   14    -	  to represent semicircle

	      3  53   17   12    -



	r (radius) = 100 pixels (3 inches on XGP)
	a (line width) = 3 pixels

W differences →   0    1    2    3

X differences ↓
	      0	 76   76    -	 -

	      1  23   15   15    -
					← number of segments needed
	      2  19    9    6    -	  to represent semicircle

	      3  19    9    6    -


The existing scheme on the XGP corresponds to the (1,0) element in
each table, which is not a bad choice (66 segments for the large
circle versus 477 using the (0,0) approximation), but there appear
to be other good choices as well.  For example, (2,1) offers another
factor of three reduction in number of segments.   The question is,
does the corresponding reduction in segment set-up time more than
compensate for the additional two ADDs required in the inner loop.

		A QUICKIE CIRCLE GENERATOR
This section is unrelated to the main purpose of the document, but
describes a simple way of generating circles for a raster device if
you wanted to do a lot of that sort of thing. 

Use the appropriate combination of equations (3-6) to get starting
values for x and W, then generate values of x and W for successive
raster lines by iterating the following.
	x ← x + y/x
	W ← 2*|x|		[top and bottom]
	W ← a*r/|x|		[both sides]
This seems to do a very nice job except for very tiny circles.